#include "Map.cpp"

// 在图中找到v0到w0的最短路径
//1. 首先最短路径我们选择使用广度优先遍历的算法遍历图
//2. 通过一个visited数组记录元素是否被访问,如果被访问过就设为true,确保每个节点只被访问依次,那么我们可以保证从v0到w0是最短路径
//2. 同时我们通过pre数组来记录每一个节点的前驱节点.在遍历完图以后,我们可以通过倒退pre数组,来找到一跳从w0到v0的路径,同时通过栈将其反过来,找到v0到w0的最短路径.

void BFSForGraph(Graph g,int v0,int w0) {
    queue<int> Q;
    bool visited[g->vexnum+1];
    int pre[g->vexnum+1];
    for (int i = 0; i < g->vexnum+1; ++i) {
        visited[i] = false;
        pre[i] = -1;
    }
    initQueue(Q);
    enterQueue(Q, v0);
    visited[v0] = true;
    visit(v0);
    //首先最短路径我们选择使用广度优先遍历的算法遍历图
    while(!EmptyQueue(Q)) {
        int v;
        deleteQueue(Q, &v);
        ArcNode* w = g->vertex[v]->firstArc;
        while (w != NULL) {
            //通过一个visited数组记录元素是否被访问,如果被访问过就设为true,确保每个节点只被访问依次,那么我们可以保证从v0到w0是最短路径
            if (!visited[w->adj]) {
                visit(w->adj);
                visited[w->adj] = true;
                //同时我们通过pre数组来记录每一个节点的前驱节点.
                pre[w->adj] = v;
                enterQueue(Q, w->adj);
            }
            w = w->next;
        }
    }
    //在遍历完图以后,我们可以通过倒推pre数组,来找到一跳从w0到v0的路径
    stack<int> s;
    int pos = w0;
    while (pre[pos] != -1) {
        s.push(pre[pos]);
        pos = pre[pos];
    }
    // 同时通过栈将其反过来,找到v0到w0的最短路径.
    while (!s.empty()) {
        int data = s.top();
        s.pop();
        visit(data);
    }
}


//  1 - 2 - 3
//   \ /
//    4

int main() {
    Graph g = CreateGraphByFile("Map.txt");
    BFSForGraph(g,1,3);
}